1307. Наибольшая грань

Гранью (border, verge, brink) строки  называется любой собственный префикс этой строки, который совпадает с её суффиксом.

Например, строка S = abaababaabaab имеет две непустые грани: ab и abaab.

Строка S = abaabaab также имеет две такие грани – ab и abaab, при этом вторая грань является перекрывающейся.

Строка длины n, состоящая из повторяющегося символа (например, aaaaaaaa или a⁸), имеет n – 1 грань. Для S = a⁸ это грани: a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa.

Понятие “собственный префикс” исключает грань, совпадающую со всей строкой.

Длина грани – это количество символов в ней.

Естественным обобщением понятия “грань” является “наибольшая грань” – максимальный по длине собственный префикс строки, совпадающий с её суффиксом.

Вход. Одна строка S (|S| ≤ 10⁶).

Выход. Выведите длину наибольшей грани строки S.

Пример входа	Пример выхода
abaabaab	5

РЕШЕНИЕ

строки – префикс-функция

Анализ алгоритма

Построим для строки S в массиве p префикс-функцию. Если длина строки S равна n, то для решения задачи достаточно вывести значение p[n – 1].

Реализация алгоритма

Префикс-функцию входной строки s строим в массиве p.

string s;

vector<int> p;

Функция MaxBorderArray вычисляет префикс-функцию для строки s.

vector<int> MaxBorderArray(string &s)

{

vector<int> p(s.size()); // p[0] = 0

for (int i = 1; i < s.size(); i++)

{

int j = p[i - 1];

while ((j > 0) && (s[i] != s[j]))

j = p[j - 1];

if (s[i] == s[j]) p[i] = j + 1; else p[i] = 0;

}

return p;

}

Строим префикс-функцию для строки s при помощи функции MaxBorderArray.

cin >> s;

p = MaxBorderArray(s);

Выводим длину наибольшей грани строки, которая находится в p[s.size() – 1].

printf("%d\n", p[s.size() - 1]);